package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	root := &TreeNode{Val: preorder[0]}
	if len(preorder) == 1 {
		return root
	}
	leftLen := 0
	for i, v := range inorder {
		if v == preorder[0] {
			leftLen = i
			break
		}
	}
	root.Left = buildTree(preorder[1:leftLen+1], inorder[0:leftLen])
	root.Right = buildTree(preorder[leftLen+1:], inorder[leftLen+1:])
	return root
}

func main() {
	preorer := []int{3, 9, 20, 15, 7}
	inorder := []int{9, 3, 15, 20, 7}
	r := buildTree(preorer, inorder)
	println(r)
}
